#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"xh.h"
AvlTree MakeEmpty(AvlTree T) {
	if (T != NULL) {
		MakeEmpty(T->left);
		MakeEmpty(T->right);
		free(T);
	}
	return T;
}

position Find(AvlTree T, ElementType x) {
	if (T == NULL) {
		printf("AvlTree is Empty!");
		return NULL;
	}

	else if (x > T->element) {
		return Find(T->right, x);
	}

	else if (x < T->element) {
		return Find(T->left, x);
	}

	else
	    return T;
}

position Findmin(AvlTree T) {
	if (T == NULL) {
		printf("AvlTree is Empty!");
		return NULL;
	}

	else if (T->left == NULL) {
		return T;
	}

	else
		return Findmin(T->left);
}

position Findmax(AvlTree T) {
	if (T == NULL) {
		printf("AvlTree is Empty!");
		return NULL;
	}

	if (T->right == NULL) {
		return T;
	}

	else
		return Findmax(T->right);
}

AvlTree Insert(AvlTree T, ElementType x) {
	if (T == NULL) {
		T = malloc(sizeof(struct AvlNode));
		if (T == NULL) {
			printf("Create AVL Tree ERROR\n");
			exit(0);
		}

		T->element = x;
		T->Height = 0;
		T->left = T->right = NULL;
	}
	else if (x < T->element) {
		T->left = Insert(T->left,x);

		if (Height(T->left) - Height(T->right) == 2) { 
			if (x < T->left->element)
				T = SingleRotateWithleft(T);
			else
				T = DoubleRotateWithleft(T);
		}
	}
	else if (x > T->element) {
		T->right = Insert(T->right,x);

		if (Height(T->right) - Height(T->left) == 2) {
			if (x > T->right->element)
				T = SingleRotateWithright(T);
			else
				T = DoubleRotateWithright(T);
		}
	}
	T->Height = Max(Height(T->left), Height(T->right)) + 1;
	return T;
}


static position SingleRotateWithright(position k2) {
	position k1;
	k1 = k2->right;
	k2->right = k1->left;
	k1->left = k2;

	k1->Height = Max(Height(k1->left), Height(k1->right)) + 1;
	k2->Height = Max(Height(k2->left), Height(k2->right)) + 1;

	return k1;
}

static position SingleRotateWithleft(position k1) {
	position k2;
	k2 = k1->left;
	k1->left = k2->right;
	k2->right = k1;

	k1->Height = Max(Height(k1->left), Height(k1->right)) + 1;
	k2->Height = Max(Height(k2->left), Height(k2->right)) + 1;

	return k2;
}

static position DoubleRotateWithleft(position k3) {
	k3->left = SingleRotateWithright(k3->left);

	return SingleRotateWithleft(k3);
}

static position DoubleRotateWithright(position k3) {
	k3->right = SingleRotateWithleft(k3->right);

	return SingleRotateWithright(k3);
}


AvlTree Delete(AvlTree T, ElementType x) {
	if (T == NULL) {
		printf("Tree is null, delete fail\n");
		return NULL;
	}

	if (x < T->element)
		T->left = Delete(T->left, x);

	if (Height(T->left) - Height(T->right) == 2) {
		if (x < T->left->element)
			T = SingleRotateWithleft(T);
		else
			T = DoubleRotateWithleft(T);
	}

	else if (x > T->element)
		T->right = Delete(T->right, x);

	if (Height(T->right) - Height(T->left) == 2) {
		if (x > T->right->element)
			T = SingleRotateWithright(T);
		else
			T = DoubleRotateWithright(T);
	}
	else {
		AvlTree TmpCell;
		if (T->left && T->right) {
			TmpCell = Findmin(T->right);
			T->element = TmpCell->element;
			T->right = Delete(T->right, T->element);
		}
		else {
			TmpCell = T;
			if (T->left == NULL)
				T = T->right;
			else if (T->right == NULL)
				T = T->left;
			free(TmpCell);
		}
	}
	if(T!=NULL)
		T->Height = Max(Height(T->left), Height(T->right)) + 1;
	return T;
}


void FirstshowTree(AvlTree T) {
	if (T != NULL) {
		printf("%d ", T->element);
		FirstshowTree(T->left);
		FirstshowTree(T->right);
	}
}

void MidshowTree(AvlTree T) {
	if (T != NULL) {
		MidshowTree(T->left);
		printf("%d ", T->element);
		MidshowTree(T->right);
	}
}

void LastshowTree(AvlTree T) {
	if (T != NULL) {
		LastshowTree(T->left);
		LastshowTree(T->right);
		printf("%d ", T->element);
	}
}
	
int Height(position P) {
	if (P == NULL) {
		return -1;
	}
	else {
		return P->Height;
	}
	
}
int Max(int a,int b) {
	return a > b ? a : b;
}